package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/10/19
 * @description: 102. 二叉树的层次遍历
 * B
 * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
 * <p>
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [9,20],
 * [15,7]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class BinaryTreeLevelOrderTraversal102B {

	/**
	 * 思路：宽度优先遍历
	 * 通过队列将当层节点存储，然后出队列将下层节点入队。
	 * ——》优化一下，入队放在一个循环里
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		if (root==null){
			return result;
		}
		///ArrayQueue();
		LinkedList<TreeNode> tempQueue = new LinkedList<>();
		tempQueue.add(root);
		while (!tempQueue.isEmpty()) {
			List<Integer> temp = new ArrayList<>();
			///想要确定当层的数量，通过一个变量进行定义
			int len = tempQueue.size();
			for (int i = 0; i < len; i++) {
				TreeNode tempNode = tempQueue.poll();
				if (tempNode.left!=null){
					tempQueue.add(tempNode.left);
				}
				if (tempNode.right!=null){
					tempQueue.add(tempNode.right);
				}
				temp.add(tempNode.val);
			}
			result.add(temp);
		}
		return result;
	}


}
